#include <iostream>
#include <vector>

#include <queue>
#include <tuple>

using namespace std;

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size();
        int n = maze[0].size();
        vector<pair<int, int>> directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        queue<tuple<int, int, int>> q;
        q.push({ entrance[0], entrance[1], 0 });
        maze[entrance[0]][entrance[1]] = '+';
        while (!q.empty()) {
            auto [r, c, steps] = q.front();
            q.pop();
            if ((r == 0 || r == m - 1 || c == 0 || c == n - 1) &&
                !(r == entrance[0] && c == entrance[1])) {
                return steps;
            }
            for (auto [dr, dc] : directions) {
                int nr = r + dr;
                int nc = c + dc;
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && maze[nr][nc] == '.') {
                    maze[nr][nc] = '+';
                    q.push({ nr, nc, steps + 1 });
                }
            }
        }

        return -1;
    }
};